"""
https://leetcode.cn/problems/validate-binary-search-tree/description/

98. 验证二叉搜索树
已解答
中等
相关标签
premium lock icon
相关企业
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
 

示例 1：


输入：root = [2,1,3]
输出：true
示例 2：


输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。
 

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

"""

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import List, Optional
from tree_node import TreeNode,build_tree_node


class Solution:
    """
    验证顺序性，一种方式是以中序遍历方式收集
    最后结果如果是个递增数组，则说明二叉搜索树
    """

    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        arr=[]
        def inorder(root:TreeNode):
            if not root:
                return
            inorder(root.left)
            nonlocal arr
            arr.append(root.val)
            inorder(root.right)

        inorder(root)

        for i in range(len(arr)-1):
            if arr[i]>=arr[i+1]:
                return False

        return True
    
if __name__=='__main__':
    arr=[5,1,4,None,None,3,6]
    root=build_tree_node(arr)

    s=Solution()
    res=s.isValidBST(root)
    print(res)